
$vertex_degree = Queue.new
$vertices_for_degree_hash = Hash.new
$adjoinable_vertices = Hash.new
$genomes = Queue.new
$ans = []
$m = -1
$degree_backup = []
$hist = []

def filter_adjoinables!(vertices, v)
  v.adjList.each { |w|
    vertices.delete(w)
  }
  vertices.delete(v)
end

def compute_k(g)
  n = g.count_v

  max_degree = 0
  degrees = []
  g.vertices.each { |v|

      #get degree of v (i.e. num of neighbours)
      degree = v.adjList.size
      degrees << degree  if $vertices_for_degree_hash[degree].nil?
      $vertices_for_degree_hash[degree] ||= []
      $vertices_for_degree_hash[degree] << v
      max_degree = degree if degree > max_degree
  }

  $m = max_degree

  degrees.sort!
  degrees.each { |degree|
    $vertex_degree.enqueue(degree)
    $degree_backup << degree
  }

  #compute sufficient size for maximum independent set
  sufficient_size = ( n / (max_degree+1.0) ).ceil

  puts
  puts "n=#{n}, max_degree=#{max_degree}, k=#{sufficient_size}"

  return sufficient_size
end


def first_gen(g)

  smallest_degree = $vertex_degree.dequeue
  puts
  puts "smallest degree = #{smallest_degree}"
  candidate_vertices = $vertices_for_degree_hash[smallest_degree]

  candidate_vertices.each { |v|
    puts "candidate vertex: #{v}"
    p = [v]
    $genomes.enqueue(p)
    $adjoinable_vertices[p] = g.vertices.clone
    filter_adjoinables!($adjoinable_vertices[p], v)
  }

end


def degree_count(g)
 temp=[]
 g.vertices.each {|v| temp<<v.adjList.size}
 temp.sort!
 return temp
end


def next_gen(g, t = 1)
  return if $genomes.is_empty?

  next_gen_genomes = Queue.new

  while !$genomes.is_empty?
    p = $genomes.dequeue
    candidate_vertices = []
    #$vertex_degree.enqueue($m) if $vertex_degree.is_empty?

    #$degree_backup.each {|d|
      #next if d < initial_degree
      #$vertex_degree = Queue.new
      #$vertex_degree.enqueue(d)
    #}

    i = 1
    t.times {
    while candidate_vertices.size == 0 && i < $degree_backup.size
      smallest_degree = $degree_backup[i]
      candidate_vertices = $adjoinable_vertices[p] & $vertices_for_degree_hash[smallest_degree]
      i+=1
    end
    }
    candidate_vertices.each { |v|
    temp_p = p.clone
    temp_p << v
    $adjoinable_vertices[temp_p] = $adjoinable_vertices[p]
    filter_adjoinables!($adjoinable_vertices[temp_p], v)
    $ans << temp_p if $adjoinable_vertices[temp_p].size == 0
    next_gen_genomes.enqueue(temp_p)
    $hist << temp_p
  }
  end

  $genomes = next_gen_genomes

  selection(g)
  next_gen(g, t+1)
end

def selection(g)
  population = []
  temp_genomes = []

  while !$genomes.is_empty?
    population << $genomes.dequeue
  end

  population.each { |p|
    population.each { |q|
      next if p == q

      p_new = ( p | q )
      is_adjoinable = true
      (( p_new | q ) - ( p_new & q )).each { |v|
        if (v.adjList & p_new).size != 0
          is_adjoinable = false
          break
        end
      }
      if is_adjoinable
        p_new.sort! { |x, y| x.value <=> y.value }
        temp_genomes << p_new
      end
    }
  }

  if temp_genomes.size == 0
    population.each { |p|
      $genomes.enqueue(p)
      $hist << p
    }
    return $genomes
  end

  temp_genomes.uniq!

  temp_genomes.each { |p|
    $genomes.enqueue(p)
    $hist << p
    $adjoinable_vertices[p] = g.vertices.clone
    p.each { |v|
      filter_adjoinables!($adjoinable_vertices[p], v)
      $ans << p if $adjoinable_vertices[p].size == 0
    }
  }

  selection(g)

end

def run(g)
   k = compute_k(g)
  first_gen(g)
end

def run_gen(g)

  k = compute_k(g)
  first_gen(g)
  next_gen(g)

  ans = []
  $ans.each { |a|
    ans = a if a.size > ans.size
  }

  return ans

end
